// 思路：二分法，是有序数组，用left，right两个指针，取中间位置元素的值midVal和target比较，
// 如果target大于midVal，那么更新left的值为mid + 1
// 如果target小于midVal，那么更新right的值为mid
// 否则返回索引，如果没有找到，最后返回-1

// 时间复杂度：O(logn)
// 空间复杂度：O(1)

// 左闭右开
function search(arr, target) {
    let left = 0
    let right = arr.length
    while (left < right) {
        let mid = Math.floor((right - left) / 2) + left
        if (target > arr[mid]) {
            left = mid + 1
        } else if (target < arr[mid]) {
            right = mid
        } else {
            return mid
        }
    }
    return -1
}

let arr = [1, 3, 4, 7, 8, 9]
console.log(search(arr, 7))

// 左闭右闭
function search2(arr, target) {
    let left = 0
    let right = arr.length - 1
    while (left <= right) {
        let mid = Math.floor((right - left) / 2) + left
        if (target > arr[mid]) {
            left = mid + 1
        } else if (target < arr[mid]) {
            right = mid - 1
        } else {
            return mid
        }
    }
    return -1
}

console.log(search2(arr, 7))